// Copyright [2020] <unknown>
#include <bits/stdc++.h>
using namespace std;
// #define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#define dbg(x...) { cerr << "\033[32;1m" << #x << " -> "; err(x); }
void err() { cerr << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif

#define sz(x) ((int)x.size())

typedef long long LL;

int n, m, s, t, k;

const int N = 55, M = 1500;
namespace acm_mcmf
{
struct E
{
    int to, cp, cost, rev;
    E(int to = 0, int cp = 0, int cost = 0, int rev = 0) : to(to), cp(cp), cost(cost), rev(rev) {}
};

struct Mcmf
{
    int v, h[N], dis[N], prev[N], pree[N];
    vector<E> G[N];

    void init(int n)
    {
        v = n;
        for (int i=0; i<=v; ++i)
            G[i].clear();
    }

    void init(int n, int m, int fr[], int to[], int cp[], int w[])
    {
        init(n);
        for (int i=0; i<m; ++i)
            addEdge(fr[i], to[i], cp[i], w[i]);
    }

    void addEdge(int from, int to, int cp, int cost)
    {
        // dbg("add", from, to, cp, cost);
        G[from].emplace_back(to, cp, cost, G[to].size());
        G[to].emplace_back(from, 0, -cost, G[from].size() - 1);
    }

    bool go(int s, int t, int f, int &flow, int x, int y)
    {
        dbg("go");
        int res = 0;
        memset(h, 0, sizeof(h[0]) * (v + 1));
        // dbg("go", s, t, f, flow, x, y, G[1].size());
        while (f)
        {
            // dbg(f);
            priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
            memset(dis, 0x3f3f3f3f, sizeof(dis[0]) * (v + 1));
            dis[s] = 0;
            q.emplace(0, s);
            while (!q.empty())
            {
                auto now = q.top();
                q.pop();
                int v = now.second;
                if (dis[v] < now.first)
                    continue;
                for (int i = 0; i < (int)G[v].size(); ++i)
                {
                    E &e = G[v][i];
                    if (e.cp > 0 && dis[e.to] > dis[v] + e.cost + h[v] - h[e.to])
                    {
                        dis[e.to] = dis[v] + e.cost + h[v] - h[e.to];
                        prev[e.to] = v;
                        pree[e.to] = i;
                        q.emplace(dis[e.to], e.to);
                    }
                }
            }
            if (dis[t] == 0x3f3f3f3f)
                break;
            for (int i = 0; i <= v; ++i)
                h[i] += dis[i];
            int d = f;
            for (int v = t; v != s; v = prev[v])
                d = min(d, G[prev[v]][pree[v]].cp);
            f -= d;
            flow += d;
            res += d * h[t];

            for (int v = t; v != s; v = prev[v])
            {
                // dbg(v);
                E &e = G[prev[v]][pree[v]];
                e.cp -= d;
                G[v][e.rev].cp += d;
            }
            

            dbg(d, h[t], x, y, f);
            if (h[t] > y) return false;
            x -= (y - h[t] + 1) * d;
            dbg(x, y);
            if (x <= 0) {
                dbg("YES");
                return true;
            }



        }
        return false;
        return res;
    }
};
} // namespace mcf

acm_mcmf::Mcmf mcf;

static int u[M], v[M], w[M], cost[M];

bool check(int mid) {
    mcf.init(n);
    mcf.init(n, m, u, v, w, cost);
    int f = 0;
    return mcf.go(s, t, 0x3f3f3f3f, f, k, mid);
}


int main(int argc, char const *argv[]) {
    // code
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    // cin >> m >> v >> e >> s >> t;
    cin >> k >> n >> m >> s >> t;
    
    for (int i=0; i<m; ++i) {
        cin >> u[i] >> v[i] >> w[i];
        cost[i] = 1;
    }

    int l = 0, r = 500000;
    while (l < r-1) {
        int mid = (l+r) >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid;
    }
    printf("%d\n", r);
    return 0;
}
